package com.demo.java.OD201_250.OD222;

import java.util.*;
import java.util.stream.IntStream;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【工作安排 | 最大报酬】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145915454
 */
public class OdMain {
    public static void main(String[] args) {
        // 读取输入数据
        try (Scanner s = new Scanner(System.in)) {
            int T = s.nextInt();  // 最大时间
            int n = s.nextInt();  // 工作数
            // 读取每个工作的时间和报酬
            int[][] jobs = IntStream.range(0, n)
                    .mapToObj(i -> new int[]{s.nextInt(), s.nextInt()})
                    .toArray(int[][]::new);
            // 通过动态规划求解最大报酬
            int res = solveMethod(jobs, T);
            // 输出结果
            System.out.println(res);
        }
    }

    // 动态规划求解方法
    private static int solveMethod(int[][] jobs, int T) {
        // 创建一个数组 dp，表示在时间限制为 t 时的最大报酬
        int[] dp = new int[T + 1];

        // 遍历每一个工作
        for (int i = 0; i < jobs.length; i++) {
            int time = jobs[i][0];  // 当前工作的时间
            int reward = jobs[i][1];  // 当前工作的报酬
            // 从后向前遍历 dp 数组，防止重复计算
            for (int t = T; t >= time; t--) {
                dp[t] = Math.max(dp[t], dp[t - time] + reward);
            }
        }
        // 返回最大报酬
        return dp[T];
    }
}